#include <iostream>
#include <unordered_map>
#include <list>

using std::cout;
using std::endl;
using std::list;
using std::unordered_map;

struct CacheNode
{
    CacheNode(int k, int v)
    : _key(k), _value(v)
    {}

    int _key;
    int _value;
};

class LRUCache
{
public:
    LRUCache(int capacity)
    : _capacity(capacity)
    {}
    //如果考虑要复制LRUCache对象，系统自带的复制控制函数还能满足要求吗？
    //注意：这里要考虑迭代器失效的情况

    void put(int key, int value);
    int get(int key);

private:
    int _capacity;
    list<CacheNode> _data;
    unordered_map<int, list<CacheNode>::iterator> _hashMap;
};

void LRUCache::put(int key, int value)
{
    //如果key存在，则更新其值
    auto it = _hashMap.find(key);
    if(it != _hashMap.end()) {
        it->second->_value = value;//更新完毕
        //将list中的key代表的元素移动到开头位置
        _data.splice(_data.begin(), _data, it->second);
        //更新其在hashMap中的位置
        _hashMap[key] = _data.begin();
    } else {
        //如果不存在，就插入数据
        //插入元素之前，要考虑元素的个数是否超出了capacity
        if(_data.size() == _capacity) {
            //要考虑淘汰list中的冷数据元素
            CacheNode & deleteNode = _data.back();
            //从hashMap中删除掉
            _hashMap.erase(deleteNode._key);
            _data.pop_back();
        }
        //往list的头部插入热数据
        _data.push_front(CacheNode(key, value));
        //可以防止迭代器失效的问题
        _hashMap[key] = _data.begin();
    }
}

int LRUCache::get(int key)
{
    //如果关键字key存在的情况,返回其value
    auto it = _hashMap.find(key);
    if(it != _hashMap.end()) {
        int ret = it->second->_value;
        //将key所代表的元素移动到list的头部
        _data.splice(_data.begin(), _data, it->second);
        _hashMap[key] = _data.begin();
        return ret;
    } else {
        //如果不存在的情况下，那就直接返回-1
        return -1;
    }
}

int main()
{
    LRUCache cache(2);
    cache.put(1, 1);
    cache.put(2, 2);
    cout << "get(1): " << cache.get(1) << endl;
    cache.put(3, 3);
    cout << "get(2): " << cache.get(2) << endl;
    cache.put(4, 4);
    cout << "get(1): " << cache.get(1) << endl;
    cout << "get(3): " << cache.get(3) << endl;
    cout << "get(4): " << cache.get(4) << endl;


    return 0;
}

